1. Field of the Invention
This invention relates to the field of computer processing. Specifically, this invention is a method, apparatus and computer program product for searching a data structure to extract possible matches of a one or more known patterns that may exist in the data structure through a single traversal of the data structure.
2. Background
Many computer programs use data structures. The structure and contents of these data structures often contain patterns. The patterns can be of text, a series of operations, or other construct that can be represented by a data structure. Many computer processes need to search the data structure for known patterns. Many prior art techniques for searching data structures are described in The Art of Computer Programming, vol. 3, chapter 6, by Donald E. Knuth, .COPYRGT. 1993 Addison-Wesley Publishing Co., ISBN 0-201-03803-X.
An example, non-limiting, use of data structures is provided by graphical imaging systems that allow deferred operations. Thus, as an application program invokes graphical operations on images, the operations are captured and stored in a data structure. This process continues until an operation is invoked that requires the generation of an actual image (such as a display or print operation). Once the generation operation is detected, the operations stored in the data structure are invoked to generate the actual image. The operations stored in the data structure are "atomic" operations in that they each perform a specific operation on one or more input images and result in a resultant image that can be used by a subsequent operation. One optimization that can be applied to this process is to detect known patterns of atomic operations that can be replaced by a molecular operation. A molecular operation operates on the same input images as does the recognized pattern of atomic operations, but is able to generate a resulting image without generating the intermediate images generated by the atomic operations. Thus, the performance of the imaging process is improved by replacing patterns of atomic operations in the data structure by equivalent molecular operations (or by off-loading the molecular operation to hardware). However, searching the data structure for these patterns consumes significant computational resource.
Searching for known patterns in the data structure, prior to the invention, has involved repetitive searches of the data structure--one search for each possible pattern until a pattern is matched. Each search consumes computer resources. Thus, multiple searches of the data structure for the known patterns are inefficient and decrease the performance of computers that perform such searches. A more efficient pattern search mechanism would improve the performance of such a computer. Thus, it would be advantageous to detect previously known patterns that exist within a data structure though a single search of the data structure.